# -*- coding: utf-8 -*-

"""剑指 Offer II 027. 回文链表
给定一个链表的 头节点 head ，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。 

示例 1：
输入: head = [1,2,3,3,2,1]
输出: true

示例 2：
输入: head = [1,2]
输出: false

提示：
链表 L 的长度范围为 [1, 10^5]
0 <= node.val <= 9

进阶：能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？"""


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """遍历链表，取出val到数组中，数组首尾双指针判断回文"""
    def isPalindrome(self, head: ListNode) -> bool:
        arr = []
        while head:
            arr.append(head.val)
            head = head.next
        
        left, right = 0, len(arr)-1
        ispalin = True
        while True:
            if left > right:
                break
            if arr[left] == arr[right]:
                left += 1
                right -= 1
            else:
                ispalin = False
                break
        return ispalin


if __name__ == '__main__':
    so = Solution()
    print(so.isPalindrome(ListNode(1, ListNode(2, ListNode(3, ListNode(3, ListNode(2, ListNode(1))))))))
    print(so.isPalindrome(ListNode(1, ListNode(2, ListNode(3, ListNode(3, ListNode(2, ListNode(2))))))))
    print(so.isPalindrome(ListNode(1)))

